The present invention relates to the field of data storage, and particularly to systems and methods employing a error correction algebraic decoder. More specifically, the present invention describes a key equation solver that calculates the roots of finite field polynomial equations of degree up to six, which lends itself to efficient hardware implementation and low latency direction calculation.
The use of cyclic error correcting codes in connection with the storage of data in storage devices is well established and is generally recognized as a reliability requirement for the storage system. Generally, the error correcting process involves the processing of syndrome bytes to determine the location and value of each error. Non-zero syndrome bytes result from the exclusive-ORing of error characters that are generated when data is written on the storage medium.
The number of error correction code (ECC) check characters employed depends on the desired power of the code. As an example, in many present day ECC systems used in connection with the storage of 8-bit bytes in a storage device, two check bytes are used for each error to be corrected in a codeword having a length of at most 255 byte positions. Thus, for example, six check bytes are required to correct up to three errors in a block of data having 249 data bytes and six check bytes. Six distinctive syndrome bytes are therefore generated in such a system. If there are no errors in the data word comprising the 255 bytes read from the storage device, then the six syndrome bytes are the all zero pattern. Under such a condition, no syndrome processing is required and the data word may be sent to the central processing unit. However, if one or more of the syndrome bytes are non-zero, then syndrome processing involves the process of identifying the location of the bytes in error and further identifying the error pattern for each error location.
The underlying mathematical concepts and operations involved in normal syndrome processing operations have been described in various publications. These operations and mathematical explanations generally involve first identifying the location of the errors by use of what has been referred to as the xe2x80x9cerror locator polynomialxe2x80x9d. The overall objective of the mathematics involved employing the error locator polynomial is to define the locations of the bytes in error by using only the syndrome bytes that are generated in the system.
The error locator polynomial has been conventionally employed as the start of the mathematical analysis to express error locations in terms of syndromes, so that binary logic may be employed to decode the syndrome bytes into first identifying the locations in error, in order to enable the associated hardware to identify the error patterns in each location. Moreover, error locations in an on-the-fly ECC used in storage or communication systems are calculated as roots of the error locator polynomial.
Several decoding techniques have been used to improve the decoding performance. One such technique is minimum distance decoding whose error correcting capability relies only upon algebraic redundancy of the code. However, the minimum distance decoding determines a code word closest to a received word on the basis of the algebraic property of the code, and the error probability of each digit of the received word does not attribute to the decoding. That is, the error probability of respective digits are all regarded as equal, and the decoding becomes erroneous when the number of error bits exceeds a value allowed by the error correcting capability which depends on the code distance.
Another more effective decoding technique is the maximum likelihood decoding according to which the probabilities of code words regarded to have been transmitted are calculated using the error probability of each bit, and a code word with the maximum probability is delivered as the result of decoding. This maximum likelihood decoding permits the correction of errors exceeding in number the error correcting capability. However, the maximum likelihood decoding technique is quite complex and requires significant resources to implement. In addition, the implementation of the maximum likelihood decoding technique typically disregards valuable data such as bit reliability information.
However, in conventional decoding schemes the Reed Solomon code is not optimized to create the maximum number of erasures for given reliability/parity information, mainly due to the fact that such information is largely unavailable to the Reed Solomon decoder. Furthermore, the key equation solvers implemented in conventional decoders are not designed to solve a weighted rational interpolation problem.
Thus, there is still a need for a decoding method that reduces the complexity and resulting latency of the likelihood decoding technique, without significantly affecting its performance, and without losing bit reliability information.
Attempts to render the decoding process more efficient have been proposed. Reference is made to N. Kamiya, xe2x80x9cOn Acceptance Criterion for Efficient Successive Errors-and-Erasures Decoding of Reed-Solomon and BCH Codes,xe2x80x9d IEEE Transactions on Information Theory, Vol. 43, No. 5, September 1997, pages 1477 -1488. However, such attempts generally require multiple recursions to calculate the error locator and evaluator polynomials, thus requiring redundancy in valuable storage space. In addition, such attempts typically include a key equation solver whose function is limited to finite field arithmetic, thus requiring a separate module to perform finite precision real arithmetic, which increases the implementation cost of the decoding process.
In addition, the decoder of a linear cyclic error correction code, specifically for Reed-Solomon Error correcting code, calculates the error locator polynomial from the syndromes by using an iterative algorithm called the key equation solver. Once the error locator polynomial coefficients have been calculated, the roots of this polynomial, which are the error locations, need to be found.
The subject of this invention addresses the process of finding the roots of such a polynomial equation. Generally, a simple procedure known as Chien search, which is an iterative search over all possible finite field elements, can be used. The problem associated with this solution is the resulting latency which is as long as the number of codeword symbols. Though it might be possible to speed up the search by conducting several parallel searches, this solution will require the storage of as many copies of the polynomial coefficients as parallel searches used, as well as employing as many sets of constant multipliers as the number of searches used. This would necessitate excessive use of hardware.
There is thus a need for a method by which roots of finite field polynomial equations can be computed in a direct, non-iterative manner. This method becomes increasingly more complicated when used to solve, in a direct manner, polynomial equations of degree higher than four. As an example, a method of linearizing the algebraic problem and solving for the roots by using Gaussian elimination, converts the polynomial into a matrix and reduces the Gaussian elimination to an efficient circuit implementation. The transformations required to reduce the polynomial to a matrix become increasingly complex as the degree of the polynomial of the equation to be solved increases. Furthermore, the processing of the solutions of the Gaussian elimination required to reduce them to the roots of the original polynomial equation become increasingly complex as the degree of the original polynomial increases. Reference is also made to U.S. Pat. No. 6,154,868 to Cox, et al., titled xe2x80x9cMethod and Means for Computationally Efficient On-The-Fly Error Correction in Linear Cyclic Codes Using Ultra-Fast Error Location,xe2x80x9d which is assigned to the same assignee as the present invention, and which is incorporated herein by reference, and to Hassner et al., xe2x80x9cRoot Finding Algorithms for GF(2-8) Polynomial Equations of Degree up to 4,xe2x80x9d IBM Technical Disclosure Bulletin, Vol. 34, No. 4B, September 1991.
There is thus a further need to simplify the calculations involved in the transformation of the polynomial to a matrix as well as to introduce a simplifying structure into the set of Gaussian elimination solutions.
In accordance with the present invention, an error correction algebraic decoder and an associated algebraic algorithm that use a key equation solver for calculating the roots of finite field polynomial equations of degree up to six, which lends itself to efficient hardware implementation and low latency direction calculation.
The key equation solver generally uses a two-step process. The first step is the conversion of quintic equations into sextic equations, and the second step is the adoption of an invertible Tschirnhausen transformation to reduce the sextic equations by eliminating the degree 5 term. The application of the Tschirnhausen transformation considerably decreases the complexity of the operations required in the transformation of the polynomial equation into a matrix.
The second step represents an algorithm that defines a specific Gaussian elimination problem, such that an arbitrary solution of this elimination leads to the splitting of the problem of solving quintic and sextic polynomial equations into a problem of finding roots of a quadratic equation and a quartic equation.